Scheduling of Railway Maintainance Projects

Mathematical Optimization Course Exam Project

SDIC Master Degree, University of Trieste (UniTS)

2024-2025

Improving the scheduling of railway maintainance projects by minimizing passengers delays subject to event requests of railway operators through mixed integer linear programming optimisation.

Presentation

Report bug

Request Feature

Table of Contents                             1. Author Info  2. About The Project          - Quick Overview          - Quick Set-Up          - Built With          - Project Structure  3. Getting Started / Installation  4. Usage Examples  5. Model Description          - Problem Description          - Decision Variables          - Objective and Constraints          - Simulated Annealing Meta-Heuristic          - Valid Inequalities          - Dataset Generation  6. Results and Scalability Analysis  7. Contributing  8. License  9. References 10. Acknowledgments

Author Info

Name	Surname	Student ID	UniTS mail	Google mail	Master
Marco	Tallone	SM3600002	marco.tallone@studenti.units.it	marcotallone85@gmail.com	SDIC

Warning

Copyright Notice:
This project is based on the work published in the referenced paper by Y.R. de Weert et al. [1] and aims to reproduce the results and implement the models originally presented by the authors in the context of a university exam project.
The main contribution proposed in this repository is limited to the personal implementation of the models and the development of the new datasets to assess their performance (which might slightly differ from the ones proposed by the original authors).

(back to top)

About The Project

Quick Overview

This project implements the mixed integer linear programming (MILP) models proposed by Y.R. de Weert et al. [1] that minimizes passengers delays while scheduling maintainance projects in a railway network. In summary, the main problem addressed by these models is to find a suitable schedule for maintainance jobs that have to be performed on the arcs of a railway network, in order to minimize the passengers delays while respecting the event requests of railway operators within a finite time horizon. Moreover, such models includes capacity constraints for alternative services in event request areas during the execution of the maintenance projects.
The implemented models are developed in the Python railway module and the relative job scheduling problems have been solved using the Gurobi solver. All the methods implemented in the models have been largely documented and it's therefore possible to gain futher information using the Python help() function as shown below:

import railway
help(railway.Railway)

Each model has been tested on small istances of the problem and a scalability analysis has also been performed to assess the performance of the models on larger instances as well. The datasets used for these tests have been randomly generated following the description provided in the original paper.
Futher information about the models mathematical formulation and implementation, the scheduling problem istances and the results obtained can be found in the Model Description and in the Results and Scalability Analysis sections below or in the presentation provided in this repository.

Quick Set-Up

Follow the instructions below to set up the project on your local machine:

1. Create a conda environment using the provided yaml file and activate it:

   conda env create -f mathopt-conda.yaml
   conda activate mathopt

2. Install the railway module using pip from the root folder of the project:

   pip install -e .

3. Import and use the Railway class in your Python scripts or Jupyter Notebooks:

   from railway import Railway

For further details, please continue reading the sections below.

Project Structure

The project is structured as follows:

.
├── 📂 apps             # Python scripts
│   ├── generate.py
│   ├── scalability.py
│   └── test.py
├── 📂 datasets         # Datasets
│   └── example.json
├── 📂 docs             # Presentation files
│   └── presentation
├── 🖼️ images           # Images
├── ⚜️ LICENSE          # License
├── 📒 notebooks        # Python notebooks
│   └── formulation.ipynb
├── 📃 papers           # Reference papers
├── 📜 README.md        # This file
├── 📂 results          # Scalability results
│   └── results.csv
├── 🐍 setup.py         # Python setup file
└── 📂 src              # Source files
    └── railway

Built With

(back to top)

Getting Started / Installation

Requirements

The project is developed in Python and uses the Gurobi solver for the optimisation problems, hence the installation of the following library is needed:

• gurobipy, version 12.0.0: the official Gurobi Python API, which requires to have an active Gurobi license and the solver installed on the machine. An academic license was used to develop the project.

Aside from common Python modules, the following optional Python libraries are needed in order to run some of the Jupiter Notebooks in the notebooks/ folder:

• tqdm, version 4.67.0
• holoviews, version 1.20.0
• hvplot, version 0..11.1
• bokeh, version 3.6.1
• plotly, version 6.0.1
• jupiter_bokeh

All the necessary libraries can be easily installed using the pip package manager.
Additionally, a conda environment yaml file containing all the necessary libraries for the project is provided in the root folder. To create the environment you need to have installed a working conda version and then create the environment with the following command:

conda env create -f mathopt-conda.yaml

After the environment has been created you can activate it with:

conda activate mathopt

Installation

The code presented in this repository develops the model proposed by Y.R. de Weert et al. [1] as a Python module that can easily be imported and used in common Python scripts or Jupiter Notebooks. Therefore, in order to correctly use the provided implementation, the railway module must be added to the Python path.
This can be done manually or by taking advantage of the provided setup.py file in the root directory. In the latter case, the module can be installed in editable mode, with the following command:

pip install -e .

from the root directory of the project. After that, the module can be imported in any Python script or notebook with the following import statement:

from railway import Railway

(back to top)

Usage Examples

The notebooks/ folder contains a set of Jupiter Notebooks that show how to use the implemented models to solve the scheduling problem. In particular, the folder contains $3$ notebooks (model0.ipynb, model1.ipynb and model2.ipynb) showing how to instantiate the $3$ models presented in the paper using the implemented Railway class and its methods, while the model_formulation.ipynb notebook provides a detailed description of the mathematical formulation of the models. The content of the latter is not used in practice but shows in details how each element of the mathematical formulation is implemented in practice in the final module.
Furthermore, in the apps/ folder contains the following Python scripts showing practical usage examples of the models:

• generate.py: a script that generates random istances of the scheduling problem for given parameters and saves them in the datasets/ folder as JSON files.
• test.py: a script that tests the performance of all the models and compares them on the same istances of the scheduling problem.
• scalability.py: a script that tests the scalability of the models on larger istances of the scheduling problem.

(back to top)

Model Description

In the following section a summary of the mathematical model presented by Y.R. de Weert et al. [1] is presented to better understand the scheduling problem addressed by the models implemented in this repository.

Problem Description

In the railway maintainance scheduling problem addressed by the implemented models we consider a railway network over a finite discrete time horizon

$$ T = {1, 2, \ldots, T_{end}} $$

with a set of nodes representing stations

$$ N = {1, 2, \ldots, n} $$

and a set of arcs representing the direct railway lines connecting the stations

$$ \mathcal{A} = {(i, j) \mid \forall i, j \in N, i < j} $$

where the arc $a = (i,j) \in \mathcal{A}$ represents the bidirectional connection between the $i^{th}$ and $j^{th}$ station. To each arc is associated a travel time by train $\omega^e_a \in \mathbb{R}$ and a travel time by alternative services $\omega^j_a \in \mathbb{R}$. In the case of this study, while the former is computed as the Euclidean distance between the stations (randomly placed in a unitary circle), the latter is modelled as the first one multiplied by some delay factor. To model this delay factor, the relation presented in the paper has been used:

$$ \omega^j_a = 1.35 \cdot \omega^e_a $$

In normal conditions, the travel time by train is used, while in case of maintainance jobs on the arc the travel time by alternative services is used.
Moreover, given any possible origin-desination pair $(o, d) \in N \times N \mid o \neq d$, we define the set $\Omega_{od}$ of average travel times by train from the given origin $o$ to the destination $d$. Each entry of this set is basically the sum of the travel times by train $\omega^e_a$ over the arcs of the shortest path connecting the origin and the destination.
As anticipated, in this context we consider the set of maintainance jobs

$$ J = {1, 2, \ldots, n_{\text{jobs}}} $$

that have to be scheduled on the arcs of the network. Each job $j \in J$ is characterized by a subset $\mathcal{A}_j \subseteq \mathcal{A}$ of one or more arcs on which the maintainance has to be performed and by a processing time $\pi_j \in \mathbb{N}$ representing the duration of the job itself. Simmetrically, for each arc $a \in \mathcal{A}$, we also introduce the set

$$ J_a = {j \in J \mid a \in \mathcal{A}_j} $$

of jobs that have to be scheduled on the arc $a$. Additionally, some arcs might require that a certain time interval $\tau_a \in \mathbb{N}$ has to pass between two consecutive jobs scheduled on the same arc.
In some cases, it might be the case that some subset of arcs cannot be unavailable simultaneously. Hence, the set $C$ containing combinations of arcs on which jobs cannot be scheduled at the same time is introduced.
For each time period $t \in T$, we then define the passenger deman $\phi_{odt}$ for each possible origin-destination pair, the share passengers travelling in the peak moment in time $t$ from $o$ to $d$ as $\beta_{odt}$ and the limited capacity $\Lambda_{at}$ for alternative services substituting the train transportation in case a job is scheduled on the arc $a$ at time $t$.
Trains that run on the arcs not subject to maintainance jobs are assumed to have an unlimited capacity, modelled by the variable $M \gg 1$. $M$ is set to a relatively big number and surely satisfies:

$$ M > \sum_{(o,d) \in N \times N} \sum_{t \in T} \phi_{odt} $$

One final element to introduce in this model are event requests. It might happen that, at any time $t \in T$ an event might occur that increases the passenger demand in a subset of arcs of the network. This is modelled by the set $E$ consisting of tracks segments $s$, i.e. sets of consecutive arcs of different length, for each event happening at time $t$. The capacity of the service should always be sufficient during event requests to avoid overcrowding. This is always the case when trains are operational but it might not be the case when alternative services are used in case a job has been scheduled on the arcs of the event request. In the latter case the capacity is limited to

$$ \Lambda_{st} = \sum_{a \in s} \Lambda_{at},\quad \forall s \in E, \forall t \in T $$

Finally, it's assumed that, when travelling from origin $o$ to destination $d$, passengers can consider up to $K \in \mathbb{N}$ possible alternative routes aiming for the one that minimizes the total travel time. Therefore, the set $R$ contains, for each origin-destination pair $(o,d) \in N \times N \mid o \neq d$, the $K$ shortest paths connecting the origin and the destination. These can be easily computed using Yen's algorithm once the topology of the network is known (implemented in the YenKSP() method of the Railway class) or by randomly generating them (in such case they won't necessairly be the shortest, but they can be interpreted as the "preferred paths" of the passengers).
Further assumptions made for this model are listed below:

• there is no precedence relation between jobs, i.e. jobs can be scheduled in any order
• each job has equal urgency
• jobs cannot be interrupted once started
• all passengers travelling between the same origin-destination pair at any given time choose the same route, i.e. the shortest (or the preferred) path connecting the origin and the destination
• outside event requests, the capacity of alternative services is always sufficient to avoid overcrowding

Decision Variables

The decision variables of the model are the following:

• $y_{jt}$: binary variable that is equal to 1 if job $j$ starts at time $t$, 0 otherwise
• $x_{at}$: binary variable that is equal to 1 if arc $a$ is available (by train) at time $t$, 0 otherwise
• $h_{odtk}$: binary variable that is equal to 1 if route option $k$ is used when travelling from origin $o$ to destination $d$ at time $t$, 0 otherwise
• $w_{at}$: continuous variable representing the travel time traversing arc $a$ at time $t$
• $v_{odt}$: continuous variable representing the travel time from origin $o$ to destination $d$ at time $t$

Objective and Constraints

The goal of the model is to minimize the total passenger delay in the network. The delay is defined as the increase in the travel time compared to the average travel time between an origin and a destination. According to this, the following objective function is defined:

$$ \underset{v}{\min} \sum_{(o,d) \in N \times N} \sum_{t \in T} \phi_{odt} (v_{odt} - \Omega_{odt}) \tag{1} $$

A feasible solution of this mathematical model finds a schedule such that all the jobs are scheduled within the time horizon $T_{end}$.
Therefore a constraint must be set in order for a job to be started and finished within the time horizon:

$$ \sum_{t=1}^{T_{end} - \pi_j + 1} y_{jt} = 1, \quad \forall j \in J \tag{2} $$

While a job is processed, the subset $\mathcal{A}j$ of arcs on which the job has to be performed must be unavailable for other jobs since they are occupied. This is modelled by the following constraint where, if $x{at} = 1$ then the arc $a$ is available at time $t$ and no job could had been scheduled neither at time $t$ itself nor in the prior time interval $[t - \pi_j + 1, t]$ (respecting time horizon), but if the arc is not available then each job $j$ can only start once in the time period preceeding time $t$ (hence the sum of its $y$ variables is at most $1$):

$$ x_{at} + \sum_{t'=\max(1, t-\pi_j+1)}^{\min(T_{end}, t)} y_{jt'} \leq 1, \quad \forall a \in \mathcal{A}, \forall t \in T, \forall j \in J_a \tag{3} $$

(Notice that this constraint alone still does not guarantee that jobs cannot overlap, a further constraint is added for this purpose in $(7)$).
Accordingly the travel time $w_{at}$ on an arc $a$ at time $t$ depends on the availability of the train services on that arc by the following constraint:

$$ w_{at} = \omega^e_a x_{at} + \omega^j_a (1 - x_{at}), \quad \forall a \in \mathcal{A}, \forall t \in T \tag{4} $$

Since variables $x_{at}$ are only bounded by $(3)$, an optional constraint is added to ensure the correct arc traversal time for free variables:

$$ \sum_{t \in T} x_{at} = T_{end} - \sum_{j \in J_a} \pi_j, \quad \forall a \in \mathcal{A} \tag{5} $$

In other words, the leftmost sum corresponds to the total time in which the arc $a$ is available, while the second term equals to the time horizon minus the total processing time of all jobs on the arc $a$. Logically, the two terms must be equal. Notice that cases for which the total sum of processing times in any arc (rightmost sum) is greater than the time horizon $T_{end}$ automatically correspond to infeasible solutions. Hence the second term is always positive or, at most, null.
Due to the fact that there might be multiple combinations $c$ of arcs that cannot be unavailable simultaneously according to set $C$, the following constraint is added:

$$ \sum_{a \in c} (1 - x_{at}) \leq 1, \quad \forall c \in C, \forall t \in T \tag{6} $$

Since jobs on the same arc cannot overlap in time the following constriant is needed:

$$ \sum_{j \in J_a} \sum_{t'=\max(1, t-\pi_j-\tau_a)}^{T_{end}} y_{jt'} \leq 1, \quad \forall t \in T, \forall a \in \mathcal{A} \tag{7} $$

For a track segment $s$ included in an event request the passenger flow in the peak moment of the considered time period must be less than the capacity of the alternative services:

$$ \sum_{a \in s} \sum_{(o,d) \in N \times N} \sum_{\substack{i = 1 \ a \in R_{odi}}}^K h_{odti} \beta_{odt} \phi_{odt} \leq \Lambda_{st} + M \sum_{a \in s} x_{at}, \quad \forall s \in E_t, \forall t \in T \tag{8} $$

Concerning alternative routes, we must ensure that passenger flow is served by at least one (and no more than one) of the $K$ possible routes:

$$ \sum_{i = 1}^K h_{odti} = 1, \quad \forall (o,d) \in N \times N, \forall t \in T \tag{9} $$

Accordingly, the following two constraints provide a lower and an upper bound for the travel time from origin $o$ to destination $d$ at time $t$:

$$ v_{odt} \geq \sum_{a \in R_{odi}} w_{at} - M (1 - h_{odti}), \quad \forall i \in {1,\dots,K}, \forall (o,d) \in N \times N, \forall t \in T \tag{10} $$

$$ v_{odt} \leq \sum_{a \in R_{odi}} w_{at} \tag{11} $$

In addition to these constraints, since in some cases variables could take values that are never included in any feasible solution, further constraints can be added to reduce the search space and the computational cost.
In particular, the following two constraints express the availability of arcs that are never included in any job at any given time:

$$ x_{at} = 1, \quad \forall a \in {a \in \mathcal{A} \mid J_a = \emptyset}, \forall t \in T \tag{12} $$

$$ w_{at} = \omega^e_a, \quad \forall a \in {a \in \mathcal{A} \mid J_a = \emptyset}, \forall t \in T \tag{13} $$

An additional constraint deals with event requests. Consider the $K$ possible routes to travel from an origin $o$ to a destination $d$ at time $t$. Imagine that all the considered $K$ routes pass through the same arc $a$ at some point of the path and that such arc is included in an event request at time $t$. In this case, if $\beta_{odt} \phi_{odt}$ is greater than the capacity of the alternative services $\Lambda_{at}$ for such arc, we must ensure the availability of the arc to avoid an infeasible solution. This is embodied by the following constraint:

$$ x_{at} = 1, \quad \forall (a,t) \in { \substack{(a,t) \in \mathcal{A} \times T \mid \exists s \in E_t \text{ s.t. } a \in s \\ \land\ \exists (o,d) \in N \times N \text{ s.t. } a \in R_{odi} \forall i \in {1,\dots,K} \ \land\ \beta_{odt} \phi_{odt} > \Lambda_{st}} } \tag{14} $$

Finally, given the $K$ routes from $o$ to $d$ at time $t$, if route option $\tilde{k} \in {1, \dots, K}$ is never used, we can set the associated variable $h_{odt\tilde{k}} = 0$. Hence the following constraint can be added to the model:

$$ h_{odti} = 0, \quad \forall (o, d, i) \in {(o, d, i) \in N \times N \times [K] \mid \min_{i \in [K]} \Omega_{odi} < \max_{j \neq i \in [K]} \Omega_{odj }} \tag{15} $$

All of these constraints and the cited objective function have been implemented in a Gurobi model object in the Railway class. Such model can be optimized using the optimize() method of the class, which returns the optimal solution of the scheduling problem.

Simulated Annealing Meta-Heuristic

Meta-heuristics can improve the computational times of MILP problems by providing a good initial solution guess in a reasonable amount of time. In this case, the simulated annealing meta-heuristic has been used to find a good initial solution guess for the MILP model. This algorithm is applied to find an initial guess for the set of starting times $S = {s_j \mid \forall j \in J}$ of all jobs.
The algorithm, implemented in the simulated_annealing() method of the Railway class as described in the paper [1], can be summarized in the following pseudo-code:

function simulated_annealing(
  S0: initial guess, 
  T0: initial temperature,
  c:  cooling factor,
  L:  iterations per temperature,
  STOP_CRITERION: stopping criterion
):
  S <- S0
  T <- T0
  while STOP_CRITERION do:
    for l in {1,...,L} do:
      Snew <- get_neighbor(S)
      Δf <- f(S) - f(Snew)
      if Δf >= 0:
        S <- Snew
      else:
        S <- Snew with probability exp(-Δf/T)
      end
    end
    T <- c * T
  end
  return S

In this algorithm, a new neighbor solution $S_{new}$ to a given one $S$ is generated every time by shifting the starting time of only one of the jobs in the solution and checking that such shift does not violate any constraint returning always a feasible solution.
Such algorithm hence returns a good initial guess for the starting times of all jobs, but it's possible to get the values of the associated decision variables from these in the following way:

• $y$ can be obtained by setting the values $y_{js_j} = 1$ $\forall j \in J$ where $s_j \in S$ and all the other $y_{jt}$ to 0 for the remaining times $t \in T$
• $x$ is unavailable, hence $x_{at} = 0$ only for $a \in \mathcal{A}$ and for $t \in T$ for which $t \in [s_j, s_j + \pi_j], \forall j \in J_a$
• $w$ values can be easily obtained from constraint $(4)$ once $x$ values are known
• $h$ and $v$ are computed once the other $3$ decision variables are set. In this case, for each origin-destination pair we can compute the shortest route among the $K$ given ones and set the $h$ values accordingly, while the $v$ values are simply the sum of the travel times over the arcs of the chosen shortest route

The described procedure is the one implemented in the get_vars_from_times(S) method of the Railway class. Simmmetrically, it's very easy to obtain $S$ from the decision variables if needed as implemented in the get_times_from_vars(y) method.

Valid Inequalities

To further reduce the search space and the computational cost of the MILP model, it's possible to set the following valid inequalities via the set_valid_inequalities() method implemented. These inequalities come from the ``Single Machine Scheduling'' problem:

• Sousa and Wolsey inequality for the "Single Machine Scheduling" problem [3]:

  $$ \sum_{t' \in Q_j} y_{jt'} + \sum_{\substack{j' \in J_a \ j' \neq j}} \sum_{t' \in Q'{j'}} y{j't'} \leq 1, \quad \forall a \in \mathcal{A}, \forall j \in J_a, \forall t \in T, \forall \Delta \in {2,\dots,\Delta_{max}} \tag{B1} $$

  with:

  • $Q_j = [t - \pi_j - \tau_a +1, t+ \Delta -1] \cap T$
  • $Q'{j'} = [t - \pi{j'} - \tau_a + \Delta, t] \cap T$
  • $\Delta_{max} = \underset{\substack{j' \in J_a \ j' \neq j}}{\max} (\pi_{j'} + \tau_a)$ (i.e. maximum total processing time for the other jobs on the same arc as job $j$)

• non overlapping jobs inequality:

  $$ y_{jt} + y_{j't'} \leq 1, \quad \forall a \in \mathcal{A}, \forall j, j' \in J_a, \forall t, t' \in T \mid j \neq j' \land t' \in (t - \pi_{j'} - \tau_a, t + \pi_j + \tau_a) \cap T \tag{B2} $$

Dataset Generation

Following the example provided in the generate.py script, it's possible to generate random istances of the scheduling problem for given parameters.
In particular, the implemented methods allows to generate an instance of the problem by selecting the desired total number of stations $n$, the number of jobs $n_{jobs}$, the time interval $T_{end}$, the number of alternative routes $K$ and the number of passengers in the network. With these values set, the remaining parameters of the model can be generated as explained in the following list:

• Network topology: i.e. Euclidean coordinates of the $n$ stations, with the associated travel times. These are randomly generated in a unitary circle (following the procedure presented in the paper) at model instantiation.

• $\pi_j$: processing times for each job $j$. Randomly generated in a desired range of integer values.

• $A_j$: arcs on which each job $j$ has to be performed. For each job, a random starting station is drawn from the set $N$. Then, the "length" of each job, meaning the number of arcs that the job is going to be performed on, is randomly generated in a desired range of integer values that can be given in input. Having set these, a random arc from the ones incident to the starting station is selected and added to a list of arcs for the current job and the starting station is updated to the one at the end of the selected arc. This is repeated until the desired number of arcs is reached. This process also filters out the arcs that are already included in the job list, so that no arc is selected twice for the same job. For further details, consult the __generate_Aj() method of the Railway class.

• $\tau_a$: minimum time interval between two consecutive jobs on the same arc $a$. Also in this case the user can set a minimum and maximum integer value for this parameter and the values are randomly generated in this range.

• $\phi$: passenger demand for each origin-destination pair $(o,d)$ and each time $t$. A minimum and maximum passenger demand percentages (%) can be set in the range $[0, 1]$. The integer values for the parameter are then randomly sampled between the minimum percentage mutiplied by the total number of passengers and the maximum percentage multiplied by the total number of passengers. (Total number of passengers is set at instantiation by the user).

• $\beta$: share of passengers travelling in the peak moment in time $t$ from $o$ to $d$. Uniformly randomly distributed in a set range of values that can be given in input, between $0$ and $1$.

• $\Lambda$: limited capacity for alternative services. A minimum and maximum capacity percentages (%) can be given in input in the range $[0, 1]$. The integer values for the parameter are then randomly sampled in the range having the following integer extremes: $$ \Lambda_{min} = \lfloor \frac{\text{min percentage} \cdot \text{number of passengers}}{n} \rfloor $$ $$ \Lambda_{max} = \lfloor \frac{\text{max percentage} \cdot \text{number of passengers}}{n} \rfloor $$

• $E$: event requests. The user can set a maximum number of event requests at each time $t$ (minimum is always $0$) and decide minimum and maximum length of the event request (i.e. how many arcs it is going to cover). The event requests are randomly generated similarly to how the set $A_j$ is (explained above). For further details consult the method __generate_E() of the Railway class.

• $C$: combinations of arcs on which jobs cannot be scheduled at the same time. This can be manually selected by the user at instantiation. In general, the set $C$ has been left empty in the generated datasets since it easily leads to infeasible problems given the considerable restriction that it imposes on the scheduling of jobs. However, it might be manually defined as a list of tuples, where tuples contain the arcs that cannot be unavailable at the same time.

• $R$: set possible alternative routes for each origin-destination pair. Generated using either Yen's algorithm or a random path generation algorithm to compute the $K$ shortest paths after the user has set the maximum number of alternative routes $K$ at instantiation.

Note

When a problem is generated, there is of course no guarantee that it will be feasible. For this reason, the final part of the generate.py script tries to solve the problem and solve the dataset only if a finite solution is found within a certain time limit.

(back to top)

Results and Scalability Analysis

The following tables report the detailed results of the scalability study of the models on randomly generated instances of the scheduling problem with different parameters.
For more information about the instances parameters used in this study, please refer to the original paper [1] or to the presentation slides.

• Model 0

ID	MIP gap (%)	Total Runtime (s)	Heuristics Time (s)	Nodes Explored	Iterations
1	0	0.208494	0	3	585
2	0	2.42914	0	3	4275
3	0	109.724	0	1822	62872
4	24.4837	300.006	0	68355	1.36329e+06
5	97.704	300.011	0	12006	352552
6	inf	300.004	0	1197	269428
7	142.648	300.005	0	18290	1.30904e+06
8	inf	300.003	0	1709	467013
9	inf	300.013	0	849	263175
10	0	0.944476	0	3	796
11	0	8.35033	0	3	4342
12	0	27.6682	0	3	8087
13	23.3691	300.01	0	30462	632842
14	inf	300.007	0	3358	147717
15	inf	300.198	0	365	55977
16	38.8846	300.028	0	24697	557799
17	inf	300.008	0	1069	141957
18	inf	300.116	0	102	113767
19	0	3.26851	0	3	845
20	0	50.1391	0	3	4510
21	0	152.502	0	3	12289
22	0	5.97909	0	3	3286
23	0	86.9082	0	7	16040
24	inf	300.429	0	1	30962
25	0	285.517	0	4242	30934
26	29.036	300.159	0	187	45906
27	inf	300.041	0	1	57416

• Model 1

ID	MIP gap (%)	Total Runtime (s)	Heuristics Time (s)	Nodes Explored	Iterations
1	0	17.5217	17.298	3	590
2	0	93.8309	91.4811	3	4207
3	0	202.37	120.097	1190	47530
4	25.362	328.268	28.2641	68858	1.28772e+06
5	90.7784	407.977	107.971	11596	356043
6	111.789	521.354	221.347	1162	246015
7	162.156	330.708	30.7026	10714	1.26297e+06
8	205.398	426.481	126.474	1778	363331
9	422.396	554.002	253.991	1161	185621
10	0	105.648	104.523	3	786
11	0	309.903	300.185	3	4386
12	0	331.182	300.77	3	8083
13	32.4426	413.693	113.684	27769	468593
14	93.7098	600.172	300.101	2215	103523
15	184.796	600.671	300.551	286	51204
16	37.7725	425.166	125.158	23143	472549
17	53.1671	600.575	300.534	723	102865
18	153.325	600.873	300.667	47	113804
19	0	303.976	300.196	3	845
20	0	354.088	300.198	3	4533
21	0	489.492	301.734	3	12329
22	0	305.492	300.01	2	3276
23	0	395.096	300.931	7	16056
24	2651.18	601.257	300.627	1	30962
25	0	429.392	300.07	1925	17955
26	29.1067	600.362	300.204	163	45203
27	16190.3	601.372	301.033	1	64425

• Model 2

ID	MIP gap (%)	Total Runtime (s)	Heuristics Time (s)	Nodes Explored	Iterations
1	0	17.5407	17.298	3	590
2	0	93.7163	91.4811	3	4207
3	0	253.749	120.097	1767	64653
4	26.1076	328.269	28.2641	55111	961899
5	84.0919	407.984	107.971	5706	231571
6	114.471	521.381	221.347	552	140679
7	147.688	330.708	30.7026	16325	1.18271e+06
8	207.398	426.501	126.474	1235	153426
9	539.447	554.04	253.991	423	149035
10	0	105.577	104.523	3	786
11	0	308.56	300.185	3	4386
12	0	328.789	300.77	3	8083
13	35.7519	413.694	113.684	27494	482841
14	93.6151	600.131	300.101	2154	100385
15	185.327	600.668	300.551	374	50013
16	34.5052	425.166	125.158	21153	465730
17	93.8495	600.571	300.534	1098	74175
18	159.55	600.76	300.667	17	101864
19	0	303.561	300.196	3	845
20	0	345.753	300.198	3	4533
21	0	459.02	301.734	3	12329
22	0	305.43	300.01	2	3014
23	0	399.575	300.931	3	15776
24	2652.31	601.385	300.627	1	30617
25	0	402.399	300.07	1521	13589
26	30.6964	600.432	300.204	223	46813
27	16190.3	601.613	301.033	1	59069

(back to top)

Contributing

The goal of this repository was to implement and reproduce the results of the models presented in paper by Y.R. de Weert et al. [1] in the context of a university exam project. However, if you have a suggestion that would make this better or extend its functionalities and want to share it with me, please fork the repo and create a pull request. You can also simply open an issue with the tag "enhancement" or "extension".
Suggested contribution procedure:

1. Fork the Project
2. Create your Feature Branch (git checkout -b feature/AmazingFeature)
3. Commit your Changes (git commit -m 'Add some AmazingFeature')
4. Push to the Branch (git push origin feature/AmazingFeature)
5. Open a Pull Request

(back to top)

License

Distributed under the MIT License. See LICENSE for more information.

(back to top)

References

[1] Y.R. de Weert, K. Gkiotsalitis, E.C. van Berkum, "Improving the scheduling of railway maintenance projects by minimizing passenger delays subject to event requests of railway operators", Computers & Operations Research, Volume 165, 2024, 106580, ISSN 0305-0548, https://doi.org/10.1016/j.cor.2024.106580

[2] Natashia Boland, Thomas Kalinowski, Hamish Waterer, Lanbo Zheng, "Scheduling arc maintenance jobs in a network to maximize total flow over time", Discrete Applied Mathematics, Volume 163, Part 1, 2014, Pages 34-52, ISSN 0166-218X, https://doi.org/10.1016/j.dam.2012.05.027

[3] J.P. Sousa, L.A. Wolsey, "A time indexed formulation of non-preemptive single machine scheduling problems", Mathematical Programming, Volume 54, Issue 1, February 1992, Pages 353-367, ISSN 1436-4646, https://doi.org/10.1007/BF01586059

(back to top)

Acknowledgments

• Mathematical Optimisation course material (UniTS, Spring 2024) (access restricted to UniTS students and staff)
• Best-README-Template: for the README template
• Flaticon: for the icons used in the README

(back to top)